/LMAR=0/XLINE=3/FONT#0=BAXL30[FNT,CLT]/FONT#1=BAXM30/FONT#2=BAXB30[FNT,CLT]/FONT#5=NGR25/FONT#3=SUB/FONT#4=SUP/FONT#7=SYMB30[FNT,CLT]

␈↓ ↓H␈↓␈↓ ¬πSTANFORD UNIVERSITY

␈↓ ↓H␈↓CS206  ␈↓ βZCOMPUTING WITH SYMBOLIC EXPRESSIONS  ␈↓ 
0FALL 1977

␈↓ ↓H␈↓␈↓ ¬DPROBLEM SET  1
␈↓ ↓H␈↓␈↓ ¬[Due  October 11


␈↓ ↓H␈↓αGeneral homework policy.

␈↓ ↓H␈↓        When␈αthe␈αhomework␈αinvolves␈αwriting␈αLISP␈αfunctions,␈αdebug␈αyour␈αfunctions␈αusing␈αLISP␈αat
␈↓ ↓H␈↓LOTS. Prepare a file that contains for each function the following:

␈↓ ↓H␈↓                        1) The external form of your function.
␈↓ ↓H␈↓                        2) A ␈↓↓brief␈↓ description of how it works and why.
␈↓ ↓H␈↓                        3) An internal form listing.
␈↓ ↓H␈↓                        4) Results from some representative sample runs.

␈↓ ↓H␈↓List␈α∂this␈α∂file␈α∂and␈α∂turn␈α∂it␈α∞in.␈α∂ Include␈α∂also␈α∂the␈α∂name␈α∂of␈α∞the␈α∂file␈α∂where␈α∂the␈α∂functions␈α∂live.␈α∞ (For
␈↓ ↓H␈↓grading␈αpurposes,␈αin␈αcase␈αsomething␈αis␈αnot␈αclear,␈αit␈αis␈αuseful␈αto␈αtry␈αout␈αa␈αfunction␈αon␈αsuitable␈αtest
␈↓ ↓H␈↓cases.)

␈↓ ↓H␈↓        Solutions␈α
will␈α
be␈α
put␈α
up␈α
in␈α
a␈α
file␈α
on␈αthe␈α
<CS206>␈α
directory␈α
and␈α
you␈α
will␈α
be␈α
able␈α
to␈αlist,␈α
read,
␈↓ ↓H␈↓or␈α⊃load␈α⊂and␈α⊃try␈α⊂them.␈α⊃  Late␈α⊂assignments␈α⊃are␈α⊂discouraged␈α⊃and␈α⊂will␈α⊃not␈α⊂be␈α⊃accepted␈α⊃after␈α⊂the
␈↓ ↓H␈↓solutions appear.


␈↓ ↓H␈↓αAssignment.

␈↓ ↓H␈↓        Write the following LISP functions.

␈↓ ↓H␈↓1.␈α␈↓↓foo␈αu␈↓␈α is␈αa␈αlist␈αconsisting␈αof␈αthe␈αatomic␈αelements␈αof␈αthe␈αlist␈α␈↓↓u␈↓␈αfollowed␈αby␈αa␈αlist␈αof␈αthe␈αnonatomic
␈↓ ↓H␈↓␈↓ α(elements of ␈↓↓u␈↓ preserving the order within each group.  Thus

␈↓ ↓H␈↓␈↓ ∧1␈↓↓foo[␈↓¬(A (B C) A B (D E))␈↓↓] = ␈↓¬(A A B (B C) (D E))␈↓↓␈↓ 

␈↓ ↓H␈↓2.␈α
␈↓↓prod[u,␈α
v]␈↓␈α
is␈α
the␈α∞product␈α
of␈α
the␈α
polynomials␈α
␈↓↓u␈↓␈α
and␈α∞␈↓↓v.␈↓␈α
 We␈α
consider␈α
only␈α
polynomials␈α∞in␈α
one
␈↓ ↓H␈↓␈↓ α(variable,␈α∪say␈α∪␈↓↓x,␈↓␈α∩and␈α∪represent␈α∪a␈α∪polynomial␈α∩as␈α∪a␈α∪list␈α∪of␈α∩its␈α∪coefficients␈α∪in␈α∪order␈α∩of
␈↓ ↓H␈↓␈↓ α(increasing powers of ␈↓↓x.␈↓  Thus ␈↓↓x␈↓∧3␈↓↓+x+5␈↓ is represented by ␈↓¬(5 1 0 1)␈↓.

␈↓ ↓H␈↓3.␈α␈↓↓locations[e,␈αu]␈↓␈αis␈αa␈αlist␈αof␈αthe␈αlocations␈αwhere␈α␈↓↓e␈↓␈αoccurs␈αas␈αa␈αsubexpression␈αof␈α␈↓↓u.␈↓␈α A␈αlocation␈αis␈αa
␈↓ ↓H␈↓␈↓ α(list␈α∂␈↓↓l␈↓=(β␈↓β1␈↓ ... β␈↓βn␈↓)␈α∂where␈α∂each␈α∂β␈↓βi␈↓␈α∂is␈α∂␈↓¬A␈α∂␈↓or␈α∂␈↓¬D␈α∂␈↓and␈α∂␈↓¬(Cβ␈↓β1␈↓¬R ... (Cβ␈↓βn␈↓¬R ␈↓↓u␈↓¬)...)␈↓␈α∂is␈α∂the␈α∂subexpression␈α∂at
␈↓ ↓H␈↓␈↓ α(location ␈↓↓l␈↓ in ␈↓↓u.␈↓  Thus

␈↓ ↓H␈↓␈↓ ∧N␈↓↓locations[␈↓¬Y, ␈↓↓␈↓¬(((X . Y) . Z) . X)␈↓↓] = ␈↓¬((D A A))␈↓↓␈↓ 

␈↓ ↓H␈↓4.␈α␈↓↓commons␈αx␈↓␈αis␈αa␈αlist␈αof␈αpairs.␈α The␈αset␈αof␈α␈↓↓car␈↓'s␈αof␈αthe␈αpairs␈αis␈αthe␈αset␈αof␈αsubexpressions␈αof␈αthe␈αS-
␈↓ ↓H␈↓␈↓ α(expression␈α∂␈↓↓x␈↓␈α∂that␈α⊂occur␈α∂more␈α∂than␈α⊂once␈α∂in␈α∂␈↓↓x␈↓␈α⊂and␈α∂the␈α∂␈↓↓cdr␈↓␈α⊂of␈α∂each␈α∂pair␈α⊂is␈α∂a␈α∂list␈α⊂of␈α∂the
␈↓ ↓H␈↓␈↓ α(locations where the ␈↓↓car␈↓ occurs. Thus

␈↓ ↓H␈↓␈↓ ∧%␈↓↓commons ␈↓¬(((X . Y) . Z) . X)␈↓↓ = ␈↓¬((X . ((A A A) (D))))␈↓↓␈↓